/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/range-sum-query-2d-immutable
   @Language: C++
   @Datetime: 19-06-13 15:27
   */

class NumMatrix {
	vector<vector<int> > sums;
public:
	NumMatrix(vector<vector<int> > &matrix) {
		int row=matrix.size(), col=matrix[0].size();
		sums=vector<vector<int> >(row+1,vector<int>(col+1,0));
		for(int i=0; i<row; ++i)
			for(int j=0; j<col; ++j)
				sums[i+1][j+1]=sums[i+1][j]+sums[i][j+1]-sums[i][j]+matrix[i][j];
	}

	int sumRegion(int row1, int col1, int row2, int col2) {
		return sums[row2+1][col2+1]-sums[row1][col2+1]-sums[row2+1][col1]+sums[row1][col1];
	}
};

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */
